/*
提交链接：https://leetcode.cn/problems/kth-missing-positive-number/submissions/564514780
1539. 第 k 个缺失的正整数-简单
完成日期：2024/9/13
二分搜索
*/

class Solution {  
public:  
    int findKthPositive(std::vector<int>& arr, int k) {  
        int left = 0, right = arr.size() - 1;  
        int targetMissing = k; // 目标缺失数量  
        // 二分查找，找到缺失数量最接近但不超过k的位置  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            // 计算mid位置之前的缺失数量  
            int missing = (mid >= arr.size()) ? mid + 1 : arr[mid] - mid - 1;  
            if (missing < targetMissing) {  
                // 如果缺失数量小于k，说明第k个缺失的数在mid的右边  
                left = mid + 1;  
            } else {  
                // 如果缺失数量大于或等于k，第k个缺失的数可能在mid左边或者就是mid位置（如果arr[mid]不是连续的），所以尝试缩小右边界  
                right = mid - 1;  
            }  
        }  
        // 此时left指向的位置是第一个使得左边缺失数量不小于k的位置，那么第k个缺失的数就是left+k（如果left之前的缺失数量等于k）  
        // 或者left位置的值减去左边缺失的数量与k的差值（如果left之前的缺失数量大于k）  
        // 但由于数组严格升序，且left是第一个使得左边缺失数量不小于k的位置，所以left位置的数（如果存在）一定大于left+k  
        // 因此，第k个缺失的数一定是left+k  
        return left + k;  
    }  
};